home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 7685 < prev    next >
Encoding:
Text File  |  1996-08-05  |  3.5 KB  |  153 lines
  1. Path: anvil.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Simple Program Question
  5. Date: 26 Feb 1996 15:26:52 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4gtfjsINNkec@anvil.ugrad.cs.ubc.ca>
  8. References: <4gsr9u$sk6@newsbf02.news.aol.com>
  9. NNTP-Posting-Host: anvil.ugrad.cs.ubc.ca
  10.  
  11. In article <4gsr9u$sk6@newsbf02.news.aol.com>, Tycope <tycope@aol.com> wrote:
  12. >I am trying to write a non -interactive program that calculates all
  13. >integer triples (i, j, k) such that 
  14. >0 < i < j < k < l and i + j + k = l. Print out the number of triples that
  15. >satisfy the requirements and print out every millionth triple.  Can anyone
  16. >see where I am missing the boat in the following code.  The program runs
  17. >and immediately terminates.  Thanks in advance for any feedback. 
  18.  
  19. Why don't you just solve the linear diophantine equation directly?
  20.  
  21. >#include <stdio.h>
  22. >
  23. >long int i, j, k, l;
  24. >long int count;
  25. >
  26. >int
  27. >main (void)
  28. >{
  29. >    do
  30. >    {
  31. >        (l = i + j + k);
  32. >        (i = 1);
  33. >        (j = 2);
  34. >        (k = 3);
  35. >        (i++, j++, k++);
  36. >        (++count);
  37. >    if (count % 1000000 == 0)
  38. >     {
  39. >        printf("%ld(i) + %ld(j) + %ld(k) = %ld(l)", i, j, k, l);
  40. >     }
  41. >
  42. >    } while (0 < i < j < k < l);
  43. >
  44. >    return (0);
  45. >}
  46.  
  47. Where you are missing the boat is that you are incrementing the variables
  48. together. You need to learn about nested loops.
  49.  
  50. Also, there is no such test in C as
  51.  
  52.     while (a < b < x)
  53.  
  54. This is evaluated left to right (I think--the order is not relevant, because it
  55. is not useful):
  56.  
  57.     while ((a < b) < x)
  58.  
  59. The (a < b) evaluates to a value that is 1 or zero based on whether the
  60. comparison is true. The 1 or 0 is then compared against x. This is far from
  61. what you want. The actual test is:
  62.  
  63.     .. while ((0 < i) && (i < j) && (j < k) && (k < l));
  64.  
  65. This is not what you want either, because what it means is that as soon as you
  66. find a triplet that does not satisfy the condition 0 < i ... < l, your loop
  67. will bail.
  68.  
  69.  
  70. For arbitrary l, your problem has infinite solutions, are aware of that? There
  71. is no upper limit on an integer that is the sum of three other integers. Thus a
  72. program cannot find all solutions using finite-precision arithmetic in a finite
  73. amount of time.
  74.  
  75. You need to set a goal for what values of 'l' you satisfy the other variables.
  76. There is no need to try values lower than 6, since the smallest possible
  77. triplet is obviously 1 + 2 + 3 = 6
  78.  
  79. Try something along the lines of:
  80.  
  81. #include <stdio.h>
  82.  
  83. int main()
  84. {
  85.     long i,j,k,l;
  86.  
  87.     for (l = 6; l < 100; l++) {
  88.         printf("triplets for l = %d:\n",l);
  89.         for (k = 3; k < l; k++) 
  90.             for (j = 2; j < k; j++) {
  91.                 i = l - j - k;
  92.                 if (i > 0 && i < j && i + j + k == l)
  93.                     printf("%d, %d, %d\n",i,j,k);
  94.             }
  95.     }
  96.     return 0;
  97. }
  98.  
  99. The i variable is determined by the other three since the equality must be
  100. satisified. Hence there is no innermost loop in the i variable. Of course, i 
  101. must be tested to fit the constraints. The loop initial values and test
  102. conditions for j and k ensure that j < k < l.
  103.  
  104.  
  105. Sample output:
  106.  
  107.  
  108. triplets for l = 6:
  109. 1, 2, 3
  110. triplets for l = 7:
  111. 1, 2, 4
  112. triplets for l = 8:
  113. 1, 3, 4
  114. 1, 2, 5
  115. triplets for l = 9:
  116. 2, 3, 4
  117. 1, 3, 5
  118. 1, 2, 6
  119. triplets for l = 10:
  120. 2, 3, 5
  121. 1, 4, 5
  122. 1, 3, 6
  123. 1, 2, 7
  124. triplets for l = 11:
  125. 2, 4, 5
  126. 2, 3, 6
  127. 1, 4, 6
  128. 1, 3, 7
  129. 1, 2, 8
  130. triplets for l = 12:
  131. 3, 4, 5
  132. 2, 4, 6
  133. 1, 5, 6
  134. 2, 3, 7
  135. 1, 4, 7
  136. 1, 3, 8
  137. 1, 2, 9
  138. triplets for l = 13:
  139. 3, 4, 6
  140. 2, 5, 6
  141. 2, 4, 7
  142. 1, 5, 7
  143. 2, 3, 8
  144. 1, 4, 8
  145. 1, 3, 9
  146. 1, 2, 10
  147.  
  148.  
  149. I hope this is what you want. Good luck learning the fundamentals of computer
  150. programming.
  151. -- 
  152.  
  153.